package vip.zhenzicheng.algorithm.leetcode.linked_list;

import vip.zhenzicheng.algorithm.ListNode;

/**
 * <a href="https://leetcode.cn/problems/palindrome-linked-list">回文链表 [简单]</a>
 * 给定一个链表头结点head，判断是否为回文链表。
 * input:[1,2,2,1] -> true
 * input:[1,2] -> false
 * 提示：
 * 链表中节点数目在范围[1, 105] 内
 * 0 <= Node.val <= 9
 *
 * @author zhenzicheng
 * @date: 2022-06-02 12:02
 */
public class PalindromeLinkedList_234 {

  public boolean isPalindrome(ListNode head) {
    ListNode fast = head, slow = head; // 快慢指针
    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }
    ListNode tail = reverse(slow);
    // 左右同时遍历 判断是否相等
    while (head != null && tail != null) {
      if (head.val != tail.val) {
        return false;
      }
      head = head.next;
      tail = tail.next;
    }
    return true;
  }

  /**
   * 反转链表
   *
   * @return 新的头结点
   */
  private ListNode reverse(ListNode head) {
    ListNode pre = null, next;
    while (head != null) {
      next = head.next;
      head.next = pre;
      pre = head;
      head = next;
    }
    return pre;
  }
}
